package com.xj.datastructure.sort;

import java.util.HashMap;
import java.util.Map;

/**
 * author: xiajun
 * Date: 2014-07-19
 * Time: 18-39-00
 * 合并多个有序数组
 * 思路使用最小堆
 * 1.将每个数组的第一个元素取出入堆并记录它来自哪个数组
 * 2.弹出堆顶最小的元素
 * 3.从弹出元素所在数组取下一个元素入堆
 */
public class MergeOrderArray {
    public static void main(String[] args) {
        MergeOrderArray m = new MergeOrderArray();
        int[] a = {1, 2, 3, 6, 9, 15};
        int[] b = {4, 7, 10, 30, 36, 40};
        int[] c = {20, 27, 33, 70};
        int[] e = {5, 13, 18, 19, 35, 60};
        Map<Integer, int[]> map = new HashMap<>();
        map.put(0, a);
        map.put(1, b);
        map.put(2, c);
        map.put(3, e);
        Node[] h = new Node[4];
        int[] flag = {0, 0, 0, 0};
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            h[entry.getKey()] = new Node(entry.getValue()[0], entry.getKey());
            flag[entry.getKey()] = flag[entry.getKey()] + 1;
        }
        m.buildHeap(h);
        boolean isok = false;
        while (true) {
            System.out.print(h[0].getValue() + "  ");
            int i = h[0].getIndex();
            int[] current = map.get(i);
            if (flag[i] >= current.length) {
                isok = true;
                map.remove(i);
                if (map.isEmpty()) {
                    break;
                }
                for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
                    i = entry.getKey();
                    if (flag[i] < entry.getValue().length) {
                        current = map.get(i);
                        isok = false;
                        break;
                    }
                }
            }
            if(isok){
                break;
            }
            int v = current[flag[i]];
            flag[i] = flag[i] + 1;
            Node newNode = new Node(v, i);
            h[0] = newNode;
            m.minHeapify(h, h.length, 0);

        }
    }

    public void buildHeap(Node[] h) {
        int index = getPrentId(h.length - 1);
        for (int i = index; i >= 0; i--) {
            minHeapify(h, h.length, i);
        }
    }

    public void minHeapify(Node[] h, int len, int prent) {
        int left = getLeftId(prent);
        int right = getRightId(prent);
        int index = prent;
        if (left < len && h[left].getValue() < h[prent].getValue()) {
            index = left;
        }
        if (right < len && h[right].getValue() < h[index].getValue()) {
            index = right;
        }
        if (prent != index) {
            Node tmp = h[prent];
            h[prent] = h[index];
            h[index] = tmp;
            minHeapify(h, len, index);
        }
    }

    public int getPrentId(int current) {
        return (current - 1) >> 1;
    }

    public int getLeftId(int prent) {
        return (prent << 1) + 1;
    }

    public int getRightId(int prent) {
        return (prent << 1) + 2;
    }
}

class Node {
    private int value;
    private int index;//值所在的数组

    public Node() {
    }

    public Node(int value, int index) {
        this.value = value;
        this.index = index;
    }

    int getValue() {
        return value;
    }

    void setValue(int value) {
        this.value = value;
    }

    int getIndex() {
        return index;
    }

    void setIndex(int index) {
        this.index = index;
    }
}